package com.startrek.ch02;

public class DuplicatedValuesArray2 {

    public Integer findDuplicatedValue(int[] a) {
        if (a == null || a.length == 0) {
            throw new IllegalArgumentException("Param should not be empty!");
        }

        int n = a.length;
        int start = 1; // start和end不是下标
        int end = n - 1;
        while (end >= start) {
            int mid = ((end - start) / 2) + start;
            int cnt = count(a, start, mid);
            if (end == start) { // 定位到那单个"可能"重复的数字
                if (cnt > 1)
                    return start;
                else
                    break;
            }

            if (cnt > (mid - start + 1)) // 重复出现的数字一定在前半段，即1 ~ m
                end = mid;
            else // 重复出现的数字一定在后半段，即m + 1 ~ n
                start = mid + 1;
        }
        return null;

    }

    private int count(int[] a, int start, int end) {
        int cnt = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] >= start && a[i] <= end) {
                cnt++;
            }
        }
        return cnt;
    }
}
